package javaCode;

/**
 * Created by lxy_920912 on 2017/1/18.
 */
public class LeetCode300 {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int [] subMin = new int[nums.length+1];
        subMin[1] = nums[0];
        int start = 1;
        int end = 1;


        for(int i = 1;i < nums.length;i++){
            int position = binFind(subMin,start, end,nums[i]);
            subMin[position] = nums[i];
            if(position > end){
                end++;
            }
        }
        return end;
    }
    public int binFind(int[] subMin,int start,int end,int target){
        if(start<end){
            int mid = (start+end)/2;
            if(subMin[mid] < target){
                return binFind(subMin,mid+1,end,target);
            }else if(subMin[mid] > target){
                return binFind(subMin,start,mid,target);
            }else{
                return mid;
            }
        }else{
            if(subMin[start] < target){
                return start+1;
            }else{
                return start;
            }

        }
    }
}
